import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: LENOVO
 * Date: 2024-08-13
 * Time: 19:26
 */
//都以小顶堆为例
public class HeapTest {
    int[] arr = new int[]{1,2,3,4,5,6,7,8,9,10};
    int usedSize = 10;
    private void siftDown(int parent,int usedSize) {
        int child = parent * 2 + 1;
        while (child < usedSize) {
            if (child + 1 < usedSize && arr[child + 1] < arr[child]) {
                child = child + 1;
            }
            if (arr[child] < arr[parent]) {
                int tmp = arr[parent];
                arr[parent] = arr[child];
                arr[child] = tmp;
                parent = child;
                child = parent * 2 + 1;
            } else {
                break;
            }
        }
    }
    private void siftUp(int child){
        int parent = (child - 1) / 2;       //(child - 1) / 2 = parent
        while(parent >= 0){
            if(arr[child] < arr[parent]){
                int tmp = arr[parent];
                arr[parent] = arr[child];
                arr[child] = tmp;
                child = parent;
                parent = (parent - 1) / 2;
            }else{
                break;
            }
        }
    }
    public void createHeap(){
         for (int parent = (usedSize - 1 - 1) / 2; parent >= 0 ; parent--) {
              siftDown(parent,usedSize);
         }
    }
    public void push(int key) {
        if(arr.length == usedSize){
            arr = Arrays.copyOf(arr,2 * arr.length);
        }
        arr[usedSize] = key;
        siftUp(usedSize);
        usedSize++;
    }
    public int pop() {
        int tmp = 0;
        arr[usedSize - 1] = tmp;
        arr[0] = tmp;
        usedSize--;
        siftDown(0,usedSize);
        return tmp;
    }
    public int peek(){
        return arr[0];
    }
    //从大到小排序  需要小顶堆  每次包最后一个第一个最小的和最后一个最大的交换，前面就陆续的排好了最大的
    public void heapSort(){
        int end = usedSize - 1;
        while(end > 0){
            int tmp = 0;
            tmp = arr[0];
            arr[0] = arr[end];
            arr[end] = tmp;
            siftDown(0,end);
            end--;
        }
    }
    public static void main(String[] args) {
        HeapTest heapTest = new HeapTest();
        heapTest.createHeap();
    }
}
